package Algorithm.unionFindSet;

/**
 * 1971. 寻找图中是否存在路径 https://leetcode.cn/problems/find-if-path-exists-in-graph/
 * 题目简述：给定一个n个节点的无向图和图中的边集edges，请判断节点s和d是否连通
 *
 * 并查集通常用来解决连通性问题，对于n个具有连接关系的节点，并查集可逐步插入初始化，完成后可快速判断两个节点是否连通。并查集类：
 * 1. parents数组：记录每个元素的父节点，一个集合中的根节点的父节点为自己
 * 2. 构造方法：初始化parents，在parents中将每个元素的父节点都指向自己，代表了n个独立的集合
 * 3. union(x,y)：将x和y所在的集合合并，即找到它们的根节点，将一个根节点的父节点指向另一个根节点
 * 4. findRoot(v)：查找一个节点所在集合的根节点。若当前节点不为根节点（根节点的值等于自身），则继续向上递归查找，并将返回结果设为自己的父节点，最后将其返回。
 * 5. isConnect(x,y)：判断两个节点是否连通，即看它们是否在同一个集合内，即根节点是否相同
 * 并查集参考文章：https://www.cnblogs.com/morui/p/10791044.html
 * 并查集题目合集：todo https://blog.csdn.net/qq_21539375/article/details/126945058
 */
public class ValidPath {

    /**
     * 思路：用并查集解决连通性问题。初始化一个n个节点的并查集，遍历边来union集合，最后通过isConnect判断s和d是否连通
     */
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) return true;
        //初始化并查集
        UnionFindSet unionFindSet = new UnionFindSet(n);
        //遍历每条边，由于图中的每条边均为双向边，因此将同一条边连接的两个顶点所在的集合做合并
        for (int[] edge : edges) {
            unionFindSet.union(edge[0], edge[1]);
        }
        return unionFindSet.isConnect(source, destination);
    }

    class UnionFindSet {
        //1.记录每个元素的父节点，一个集合中的根节点的父节点为自己
        int[] parents;

        //2.初始化并查集，将每个元素的父节点都指向自己，代表了n个独立的集合
        UnionFindSet(int n) {
            parents = new int[n];
            for (int i = 0;i < n;i++) {
                parents[i] = i;
            }
        }

        //3.将包含元素x的集合与包含元素y的集合合并，即找到它们的根节点，将一个根节点的父节点指向另一个根节点
        void union(int x, int y) {
            int xRoot = findRoot(x);
            int yRoot = findRoot(y);
            if (xRoot != yRoot) {
                parents[xRoot] = yRoot;
            }
        }

        //4.查找一个节点所在集合的根节点。在查找时顺带压缩路径，即将返回结果设为自己的父节点，最后将其返回。最理想的情况为所有非根节点都为叶子节点
        int findRoot(int v) {
            if (parents[v] != v) { //若当前节点不为根节点，则继续递归向上查找，并将返回结果赋值给parents[v]，压缩路径
                parents[v] = findRoot(parents[v]);
            }
            //将根节点返回
            return parents[v];
        }

        //5.判断两个节点是否连通，即看它们是否在同一个集合内，即根节点是否相同
        boolean isConnect(int source, int destination) {
            return findRoot(source) == findRoot(destination);
        }
    }

}
